#pragma once
#include "./KeyHashMap.h"
#include "./LinkList.h"
#include "../allocator/page_allocator.h"
#include <vector>
#include <list>

#ifndef WIN32
#define _countof(x) (sizeof(x) / sizeof((x)[0]))
#endif

namespace qb{
	namespace base{
		namespace container{

			//template<class Type>
			//class CachedObjectPool{
			//	typedef std::list<Type*> TypePtrList;
			//	TypePtrList		m_unused;
			//	int				m_capcity;		// 默认-1,表示全部缓存
			//	int				m_allocated;
			//public:
			//	CachedObjectPool(int capcity = -1) :m_capcity(capcity), m_allocated(0){}
			//	~CachedObjectPool(){
			//		TypePtrList::iterator it = m_unused.begin();
			//		for (; it != m_unused.end(); ++it)
			//		{
			//			delete *it;
			//		}
			//	}
			//	int GetCount()const{ return m_unused.size(); }
			//	int GetCapcity()const{ return m_capcity; }
			//	int GetAllocated()const{ return m_allocated; }
			//	void SetCapcity(int capcity){ m_capcity = capcity; }
			//	Type* Alloc(){
			//		Type* type = 0;
			//		if (!m_unused.empty())
			//		{
			//			type = m_unused.front();
			//			m_unused.pop_front();
			//		}
			//		else
			//			type = new Type();
			//		m_allocated++;
			//		return type;
			//	}
			//	void Free(Type* t){
			//		DEBUG_ASSERT(t);
			//		m_allocated--;
			//		if (m_capcity > 0 && (int)m_unused.size() >= m_capcity)
			//		{
			//			delete t;
			//		}
			//		else
			//			m_unused.push_back(t);
			//	}
			//	void Reserve(int n)
			//	{
			//		n = n <= 0 ? 0 : n;
			//		while ((int)m_unused.size() < n)
			//		{
			//			m_unused.push_back(new Type());
			//		}
			//		while ((int)m_unused.size() > n)
			//		{
			//			Type* t = m_unused.front();
			//			m_unused.pop_front();
			//			delete t;
			//		}
			//	}
			//};


			/*
				Type:
					必须有默认构造函数
			*/
			template<class Type>
			class LinkListObjectPool{
				typedef DoubleLinkList<Type> TypeLinkList;
				TypeLinkList	m_unused;
				int				m_capcity;		// 默认-1,表示全部缓存
				int				m_allocated;
			public:
				LinkListObjectPool(int capcity = -1) :m_capcity(capcity), m_allocated(0){}
				~LinkListObjectPool(){
					Type* head = m_unused.GetHead();
					while (head)
					{
						Type* temp = head;
						head = head->GetNext();
						delete temp;
					}
					m_unused.Reset();
				}
				int GetCount()const{ return m_unused.GetCount(); }
				int GetCapcity()const{ return m_capcity; }
				int GetAllocated()const{ return m_allocated; }
				void SetCapcity(int capcity){ m_capcity = capcity; }
				Type* Alloc(){
					Type* type = m_unused.PickHead();
					if (type==nullptr)
						type = new Type();
					type->SetNext(nullptr);
					type->SetPrev(nullptr);
					m_allocated++;
					return type;
				}
				void Free(Type* t){
					DEBUG_ASSERT(t);
					m_allocated--;
					if (m_capcity > 0 && (int)m_unused.GetCount() >= m_capcity)
					{
						delete t;
					}
					else
						m_unused.Append(t);
				}
				void Reserve(int n)
				{
					n = n <= 0 ? 0 : n;
					while ((int)m_unused.GetCount() < n)
					{
						m_unused.Append(new Type());
					}
					while ((int)m_unused.GetCount() > n)
					{
						Type* t = m_unused.PickHead();
						if (t)
							delete t;
					}
				}
			};

			template<class Type>
			class CachedObjectPool{
				typedef std::list<Type*> TypePtrList;
				typedef DoubleLinkList<Type> TypeLinkList;
				typedef qb::base::PageAllocator PageAllocator;
				TypeLinkList	m_unused;
				PageAllocator*	m_allocator;
				int				m_capcity;		// 默认-1,表示全部缓存
				int				m_allocated;
			public:
				CachedObjectPool(int capcity = -1) :m_capcity(capcity), m_allocated(0), m_allocator(nullptr){
					m_allocator = PageAllocator::CreateWithRoot(nullptr, false);
				}
				~CachedObjectPool(){
					Type* head = m_unused.GetHead();
					while (head)
					{
						Type* temp = head;
						head = head->GetNext();
						temp->reset();
					}
					m_unused.Reset();
					DEBUG_ASSERT(m_allocator);
					PageAllocator::Destroy(m_allocator);
					m_allocator = nullptr;
				}
				int GetCount()const{ return m_unused.GetCount(); }
				int GetCapcity()const{ return m_capcity; }
				int GetAllocated()const{ return m_allocated; }
				void SetCapcity(int capcity){ m_capcity = capcity; }
				Type* Alloc(){
					Type* type = m_unused.PickHead();
					if (type == nullptr)
					{
						void* mem = m_allocator->AllocMemory(sizeof(Type));
						type = new (mem) Type();
					}
					type->SetNext(nullptr);
					type->SetPrev(nullptr);
					m_allocated++;
					return type;
				}
				void Free(Type* t){
					DEBUG_ASSERT(t);
					m_allocated--;
					m_unused.Append(t);
				}
				void Reserve(int n){}
			};


			template<typename Entry, typename Allocator>
			class LevelNode{
				#if WIN32
				typedef typename LevelNode<Entry, Allocator> NodeType;
				typedef typename NodeType* NodePtr;
				typedef typename DoubleLinkList<NodeType> NodeQueue;
				#else
				typedef LevelNode<Entry, Allocator> NodeType;
				typedef NodeType* NodePtr;
				typedef DoubleLinkList<NodeType> NodeQueue;
				#endif
			public:
				NodePtr		m_next;		//
				NodePtr		m_prev;		// 
				NodePtr		m_parent;	// 
				NodeQueue	m_queue;	// m_queue与m_entry互斥,两者必须只有一个
				int			m_count;	// 该节点下面的所有Entry个数之和
				Entry*		m_entry;	// m_entry为空时,m_queue必定有值,
			public:
				LevelNode() :m_next(nullptr), m_prev(nullptr), m_parent(nullptr), m_entry(nullptr), m_count(0){}
				~LevelNode(){}
				void Swap(LevelNode* node)
				{
					std::swap(m_next, node->m_next);
					std::swap(m_prev, node->m_prev);
					std::swap(m_parent, node->m_parent);
					
					std::swap(m_count, node->m_count);
					m_queue.Swap(node->m_queue);
					NodePtr head = m_queue.GetHead();
					while (head)
					{
						head->SetParent(this);
						head = head->GetNext();
					}
					std::swap(m_entry, node->m_entry);
					if (m_entry)
					{
						int index = 0;
						Entry* et = m_entry;
						while (et)
						{
							BASSERT(et->GetNode() == node);
							et->SetNode(this);
							et = et->GetNext();
							index++;
						}
						BASSERT(index == m_count);
					}
					
					DEBUG_ASSERT(m_queue.CheckFull());
				}
				void reset(){ m_count = 0; m_entry = nullptr; m_parent = nullptr;  m_prev = m_next = nullptr; m_queue.Reset(); }
				void destroy(Allocator* alloc)
				{
					m_next = m_prev = m_parent = nullptr;
					m_entry = nullptr;
					m_count = 0;
					while (NodeType* cur = m_queue.PickHead())
					{
						cur->destroy(alloc);
						alloc->Free(cur);
					}
				}
			public:
				inline NodePtr GetParent()const{ return m_parent; }
				inline NodePtr GetPrev()const{ return m_prev; }
				inline NodePtr GetNext()const{ return m_next; }
				inline void SetParent(NodePtr p){ m_parent = p; }
				inline void SetNext(NodePtr n){ m_next = n; }
				inline void SetPrev(NodePtr p){ m_prev = p; }
			public:
				const NodePtr GetRoot()const{ NodePtr root = this; while (root->m_parent){ root = root->m_parent; }return root; }
				NodePtr GetRoot(){ NodePtr root = this; while (root->m_parent){ root = root->m_parent; }return root; }
				int GetRootOffset()const{
					int offset = 0;
					const NodeType* node = this;
					while (node->GetParent())
					{
						NodePtr parent = node->GetParent();
						NodePtr cur = parent->GetFirstChild();
						while (cur != node && cur)
						{
							offset += cur->size();
							cur = cur->GetNext();
						}
						node = parent;
					}
					return offset;
				}
				inline int GetChildCount()const{ return m_queue.GetCount(); }
				inline int GetSubCount()const{ return m_queue.GetCount() <= 0 ? m_count : m_queue.GetCount(); }
				inline bool IsLeaf()const{ return m_queue.GetHead() == nullptr; }
				inline NodePtr GetFirstChild()const{ return m_queue.GetHead(); }
				inline NodePtr GetLastChild()const{ return m_queue.GetTail(); }
				inline Entry* GetEntry()const{ return m_entry; }
				inline void SetEntry(Entry* entry){ 
					m_entry = entry; 
					/*if (m_parent && m_parent->GetFirstChild() == this)
						m_parent->SetEntry(entry);*/
				}
				inline Entry* GetFirstEntry()const{
					//if (m_entry)return m_entry;
					Entry* et = m_entry;
					const NodeType* child = m_queue.GetHead();
					while (child){
						et = child->m_entry;
						child = child->m_queue.GetHead();
					}
					return et;
				}
				int GetNodeCount(bool recursive)const
				{
					if (!recursive)return GetSubCount();
					int ncount = GetSubCount();
					NodePtr head = m_queue.GetHead();
					while (head)
					{
						ncount+=head->GetNodeCount(recursive);
						head = head->GetNext();
					}
					return ncount;
				}
			public:
				inline int size()const{ return m_count; }
				inline void del_count_recursively(NodePtr node)
				{
					while (node){ --node->m_count; node = node->m_parent; }
				}
				inline void add_count_recursively(NodePtr node)
				{
					while (node){ ++node->m_count; node = node->m_parent; }
				}
				void move_range_to(int start, int count, NodePtr node)
				{
					DEBUG_ASSERT(node && node->GetSubCount() <= 0 && start >= 0 && start+count <= GetSubCount() && count > 0);
					if (IsLeaf())
					{
						// 不能将双链表断裂开
						Entry* head = GetFirstEntry(); DEBUG_ASSERT(head && head->GetNode()==this);
						Entry* entry = DoubleLinkList<Entry>::GetNext(head, start);

						node->SetEntry(entry);
						node->m_count = count;
						Entry* tail = entry;
						for (int i = 0; i < count; i++)
						{
							tail->SetNode(node);
							tail = tail->GetNext();
						}
						m_count -= count;
						if (m_count <= 0)SetEntry(nullptr);
						else if (start == 0)SetEntry(tail);
						//SetEntry(m_count <= 0 ? nullptr : (start == 0 ? tail : GetEntry()));
						DEBUG_ASSERT(this->check() && node->check());
					}
					else
					{
						m_queue.Pick(start, count, node->m_queue);
						int size = 0;
						int total = this->size();
						NodePtr head=node->m_queue.GetHead();
						while (head)
						{
							size += head->size();
							head = head->GetNext();
						}
						m_count -= size;
						node->m_count = size;
						DEBUG_ASSERT(size <= total);
					}
				}
				void expand_horz(NodePtr node, Allocator* alloc)
				{
					// 水平扩展:新建一个与node同一级的节点,容纳node的后一半子节点
					DEBUG_ASSERT(node && node->GetParent() == this);
					int nsize = node->size();
					int ntotal = node->GetSubCount();
					int ncount = ntotal / 2;
					NodePtr second = alloc->Alloc();
					second->SetParent(this);
					node->move_range_to(ncount, ntotal - ncount,second);
					m_queue.InsertAfter(node, second);
					BASSERT(nsize == node->size() + second->size());
					DEBUG_ASSERT(node->GetNext() == second && second->GetPrev() == node);
					DEBUG_ASSERT(check() && second->check() && node->check());
				}
				void expand_vert(Allocator* alloc)
				{
					//纵向扩展:新建两个子节点,分别容纳当前节点的前后各一半子节点
					//		   然后这两个子节点作为中间节点,当前节点成为这两个节点的父节点
					//		   原有众多子节点作为中间节点的子节点
					int nsize = size();
					int ntotal = GetSubCount();
					int ncount = ntotal / 2;
					NodePtr first = alloc->Alloc();
					NodePtr second = alloc->Alloc();  
					first->SetParent(this);
					second->SetParent(this);
					move_range_to(0,ncount,first);
					move_range_to(0,ntotal - ncount,second);
					BASSERT(GetSubCount() == 0 && m_count == 0 && m_entry == 0);
					BASSERT(first->size() + second->size() == nsize);

					SetEntry(nullptr);
					m_count = nsize;
					DEBUG_ASSERT(m_queue.GetCount() == 0);
					m_queue.Append(first);
					m_queue.Append(second);
					DEBUG_ASSERT(first->GetPrev() == nullptr && first->GetNext() == second && second->GetPrev() == first && second->GetNext() == nullptr);
					DEBUG_ASSERT(first->size() + second->size() == nsize);
					DEBUG_ASSERT(check() && first->check() && second->check());
				}
				Entry* at_impl(int pos, const NodeType*& pnode)const
				{
					if (pos < 0 || pos >= m_count)return nullptr;
					DEBUG_ASSERT(GetParent() == nullptr);//必须是根对象
					const NodeType* node = this;
					int start=0, end=node->m_count;
					int nsub = node->GetChildCount();
					NodePtr child = node->GetFirstChild();
					while (nsub >0)
					{
						if (pos <= (start + end)>>1)
						{
							child = node->GetFirstChild();
							for (end = start + child->m_count; pos >= end; end += child->m_count)//左到右
								child = child->m_next;
							start = end - child->m_count;
						}
						else
						{
							child = node->GetLastChild();
							for (start = end-child->m_count;pos<start;start-=child->m_count)//左到右
								child = child->m_prev;
							end = start + child->m_count;
						}
						node = child;
						nsub = node->GetChildCount();
						DEBUG_ASSERT(node);
					}
					DEBUG_ASSERT(node && node->GetFirstChild() == nullptr && pos >= start && pos < end);
					Entry* first = node->GetFirstEntry();
					Entry* entry = DoubleLinkList<Entry>::GetNext(first, pos-start);
					// 区分左右可额外提升6%的性能
					DEBUG_ASSERT(entry && entry->GetNode() == node);
					pnode = node;
					return entry;
				}
				Entry* at_impl_old(int pos, NodePtr& pnode)
				{
					if (pos < 0 || pos >= m_count)return nullptr;
					//HighResTime timer; int step = 0;
					register NodePtr node = this;
					while (NodePtr child=node->GetFirstChild())
					{
						while (pos >= child->size() && child->m_next)
						{
							pos -= child->size();
							child = child->m_next;
							//step++;
						}
						if (pos >= node->size())return nullptr;
						node = child;
					}
					//BlockTimer::Get().AddPart(0,timer,step);
					DEBUG_ASSERT(node && node->GetFirstChild() == nullptr && pos >= 0 && pos < node->size());
					Entry* entry = node->GetFirstEntry();
					while (entry && pos > 0)
					{
						entry = entry->GetNext(); --pos;
					}
					DEBUG_ASSERT(entry && pos == 0 && entry->GetNode() == node);
					pnode = node;
					//BlockTimer::Get().AddPart(1, timer);
					return entry;
				}
				int find_impl(Entry* et)
				{
					NodePtr node = et ? et->GetNode() : nullptr;
					if (node && node->GetRoot() == this)
					{
						int offset = DoubleLinkList<Entry>::Find(node->GetFirstEntry(), node->size(), et);
						DEBUG_ASSERT(offset >= 0);
						offset += node->GetRootOffset();
						return offset;
					}
					return -1;
				}
				void erase_impl(NodePtr node, Entry* et, Allocator* alloc)
				{
					DEBUG_ASSERT(node->GetFirstChild() == 0 && node->GetChildCount() == 0);
					DEBUG_ASSERT(et && et->GetNode() == node && node->IsLeaf());
					del_count_recursively(node);
					Entry* first = node->GetEntry();
					if (et == first)
					{
						first = et->GetNext();
						if (first && first->GetNode() != node)
						{
							first = nullptr;
							DEBUG_ASSERT(node->size() == 0);
						}
						node->SetEntry(first);
					}
					et->SetNode(nullptr);
					DoubleLinkList<Entry>::Unlink(et);
				}
				NodePtr append_impl(Entry* e, Entry* last)
				{
					CHECK_SINGLE(e);
					if (last)
					{
						NodePtr node = last->GetNode();
						DEBUG_ASSERT(last && node && node->GetRoot() == this && node->IsLeaf() && node->GetFirstEntry() != nullptr);
						DoubleLinkList<Entry>::Link(last, e, nullptr);
						e->SetNode(node);
						NodePtr temp = node;
						while (node){ ++node->m_count; node = node->m_parent; }
						//add_count_recursively(node);
						return temp;
					}
					DEBUG_ASSERT(GetEntry() == nullptr && m_queue.GetCount() <= 0);
					e->SetNode(this);
					SetEntry(e);
					m_count = 1;
					return this;
					//return insert_impl(e, last, node, alloc);
				}
				NodePtr insert_impl(Entry* e, Entry* cur, NodePtr node, Allocator* alloc)
				{
					// 功能:将e插入到cur所在位置,cur的节点是node,插入之后,e在cur前面
					CHECK_SINGLE(e);
					DEBUG_ASSERT(node && node->IsLeaf() && this->GetParent() == nullptr && node->GetRoot() == this);
					DEBUG_ASSERT(cur && cur->GetNode() == node);
					DoubleLinkList<Entry>::Link(cur->GetPrev(), e, cur);
					if (node->GetEntry() == cur)
						node->SetEntry(e);
					e->SetNode(node);
					add_count_recursively(node);
					return node;
				}
				NodePtr balance(NodePtr node, Allocator* alloc, int expect_count, int max_count)
				{
					// 功能:对节点node进行平衡,可能会增删节点
					DEBUG_ASSERT(GetParent() == nullptr && node && node->GetRoot() == this);
					DEBUG_ASSERT(node->GetSubCount() <= node->size() && node->GetSubCount() >= 0);
					if (node->GetSubCount() > 0 && node->GetSubCount() <= max_count)
						return node;
					if (node->size() <= 0 && node != this)
					{
						// 需要将node删除并维持平衡
						DEBUG_ASSERT(node->GetSubCount() == 0);
						while (node->size() <= 0 && node != this)
						{
							NodePtr parent = node->GetParent();
							DEBUG_ASSERT(parent != nullptr && parent->m_queue.Contain(node));
							parent->m_queue.Remove(node);
							alloc->Free(node);
							node = parent;
						}
						return node;
					}

					int last_size = size();
					while (node && node->GetSubCount() > max_count)
					{
						NodePtr parent = node->GetParent();
						if (parent && parent->GetSubCount() < expect_count)
							parent->expand_horz(node, alloc);
						else
							node->expand_vert(alloc);
						node = parent;
					}
					DEBUG_ASSERT(last_size == size());
					return node;
				}
			public:
				void dump(int level)
				{
					if (IsLeaf())return;
					char indent[256] = { 0 };
					char* ptr = indent; char* end = indent + _countof(indent) - 1;
					for (int i = 0; i < level; i++)
					{
						for (int k = 0; k < 4 && ptr < end; k++)
							*ptr++ = '-';
					}
					*ptr = '\0';
#ifdef WIN32
					char buf[1024] = { 0 };
					FMTBUF(buf, "%32s type:%s  %6d  level:%4d  sub:%6d  entry:%8d", indent, IsLeaf() ? "leaf" : "node", size(),
						level, GetChildCount(),m_count);
					OutputDebugStringA(buf);
#endif
					NodePtr head = m_queue.GetHead();
					while (head)
					{
						head->dump(level + 1);
						head = head->GetNext();
					}
				}
				bool check_all()const
				{
					DEBUG_ASSERT(check());
					DEBUG_ASSERT(m_queue.CheckFull());
					NodePtr head = m_queue.GetHead();
					while (head)
					{
						DEBUG_ASSERT(head->GetParent() == this);
						DEBUG_ASSERT(head->check_all());
						DEBUG_ASSERT(head->check());
						head = head->GetNext();
					}
					return true;
				}
				bool check()const
				{
					if (IsLeaf())
					{
						int i = 0;
						Entry* cur = GetEntry();
						for (; i < m_count && cur; i++)
						{
							DEBUG_ASSERT(cur->GetNode() == this);
							cur = cur->GetNext();
						}
						DEBUG_ASSERT(i == m_count);
					}
					else
					{
						int nsum = 0;
						NodePtr cur = m_queue.GetHead();
						while (cur)
						{
							nsum += cur->size();
							cur = cur->GetNext();
						}
						DEBUG_ASSERT(nsum == m_count);
					}
					m_queue.CheckFull();
					return true;
				}
			};


			template<class Entry, class Key>
			class IteratorBase{
				int		m_index;
				Entry*	m_current;
			public:
				IteratorBase() :m_index(-1), m_current(nullptr){}
				IteratorBase(int index, Entry* entry) :m_index(index), m_current(entry){ m_index = entry ? index : (-1); }
				IteratorBase(const IteratorBase& it) :m_index(it.m_index), m_current(it.m_current){}
				IteratorBase& operator=(const IteratorBase& it){ m_index = it.m_index; m_current = it.m_current; return *this; }
				const Key& operator*()const{ static Key k = Key(); return m_current ? m_current->key : k; }
				IteratorBase& operator++(){
					m_current = m_current ? m_current->GetNext() : nullptr;
					m_index = m_current ? (m_index++) : (-1);
					return *this;
				}
				bool operator==(const IteratorBase& it)const{ return m_index == it.m_index && m_current == it.m_current; }
				bool operator!=(const IteratorBase& it)const{ return m_index != it.m_index || m_current != it.m_current; }
			};
		};//namespace container::
	}//namespace base;
}//namespace ss;
